/**
 *    Copyright (C) 2008  Victor Smirnov <aist11@gmail.com>
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License along
 *    with this program; if not, write to the Free Software Foundation, Inc.,
 *    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 *    See LICENSE.exceptions in the root folder of this project for possible
 *    exceptions
 *
 */


#include <cubefs/api/api.hpp>
#include <cubefs/core/tools/packed_map.hpp>



#include <stdlib.h>
#include <bm_tools.h>
#include <iostream>
#include <fstream>

#include <set>


using namespace cubefs;
using namespace cubefs::core;
using namespace cubefs::tools;

using namespace std;

typedef cubefs::tools::VoidValue void_value;

template <typename Key_, typename Value, typename Constants, long Indexes = 1, typename IndexKey = Key_>
class StlSet {
	typedef Key_ T;
	set<T> set_;
	BigInt idx_;

	BigInt size_;
public:
	typedef Key_ Key;

	StlSet(): idx_(0) {}

	void Add(const T& value) {
		set_.insert(value);
	}

	Int kind() const {
		return 0; //value map
	}

	BigInt max_size() const {
		return Constants::BLOCK_SIZE / sizeof(Key_);
	}

	BigInt& size() {
		return size_;
	}

	const BigInt& size() const {
		return size_;
	}

	T max_key() const
	{
		if (!set_.empty()) {
			return *set_.rend();
		}
		else {
			return 0;
		}
	}

	void Reindex() {}

	BigInt FindLT(const T& value)
	{
		if (set_.find(value) != set_.end())
		{
			return idx_++;
		}
		else {
			return 0;
		}
	}
};


template <typename Map>
class linear_task {
    Map *map;
    int reads;
    volatile long int idx;
public:
    linear_task(Map *m, int _reads): map(m), reads(_reads), idx(0) {}

    void prepare() {
        map->size() = 0;

        for (Int c = 0; c < map->max_size(); c++) {
            map->Add(map->kind() == 0 ? c*2 + 1 : 2);
        }

        map->Reindex();
    }

    void calibrate() {}

    void run() {
        typename Map::Key key = 0;
        typename Map::Key max_value = map->max_key();
        for (int c = 0; c < reads; c++) {
            key += 2;
            if (key >= max_value) {
                key = 0;
            }
            idx+= map->FindLT(key);
        }
    }
};

template <typename Map>
class random_task {
    Map *map;
    int reads;
    volatile long int idx;
public:
    random_task(Map *m, int _reads): map(m), reads(_reads), idx(0) {}

    void prepare() {
        map->size() = 0;

        for (Int c = 0; c < map->max_size(); c++) {
            map->Add(map->kind() == 0 ? c*2 + 1 : 2);
        }

        map->Reindex();
    }

    void calibrate() {
        typename Map::Key max_value = map->max_key();
        for (int c = 0; c < reads; c++) {
            idx += get_random((size_t)max_value);
        }
    }

    void run() {
        typename Map::Key max_value = map->max_key();

        for (int c = 0; c < reads; c++) {
            idx+= map->FindLT(get_random((size_t)max_value));
        }
    }
};

const int READ_COUNT =  16*1024*1024;

int runs = 4;

template <
        int BlockSize,
        int CacheLineWidth,
        template <typename Key, typename Value, typename Constants, long Indexes, typename IndexKey> class MapType,
        template <typename Map> class Task
    >
class TaskRunner {
    struct MapConstants {
        static const int BLOCK_SIZE         = BlockSize * 1024;
        static const int KIND               = 0;
        static const int CACHE_LINE_WIDTH   = CacheLineWidth;
    };

    typedef MapType<int, void_value, MapConstants, 1, long long> Map;
    
    int runs_count_;
    int reads_;

public:
    TaskRunner(int runs_count, int reads): runs_count_(runs_count), reads_(reads) {}

    long int run() {
        Map* map = new Map();
        Task<Map> task(map, reads_);


        task.prepare();

        long int time0 = getTime();

        for (int c = 0; c < runs_count_; c++) {
            task.calibrate();
        }

        time0 = getTime() - time0;

        long int time1 = getTime();
        for (int c = 0; c < runs_count_; c++) {
            task.run();
        }

        long int time2 = getTime() - time1 - time0;

        delete map;

        return time2;
    }
};

template <
        typename BlockSizeList,
        int LineWidth
>
class BlockSizeTest {

    static const int BlockSize         = BlockSizeList::Head::Value;

    typedef TaskRunner<BlockSize, LineWidth, PackedValueMap, linear_task> LVTestRunner;
    typedef TaskRunner<BlockSize, LineWidth, PackedValueMap, random_task> RVTestRunner;
//    typedef TaskRunner<BlockSize, LineWidth, PackedIndexMap, linear_task> LITestRunner;
//    typedef TaskRunner<BlockSize, LineWidth, PackedIndexMap, random_task> RITestRunner;

    typedef TaskRunner<BlockSize, LineWidth, StlSet, linear_task> LSTestRunner;
    typedef TaskRunner<BlockSize, LineWidth, StlSet, random_task> RSTestRunner;


public:
    static void run(int runs_count, int reads) {
        LVTestRunner lv_runner(runs_count, reads);
        RVTestRunner rv_runner(runs_count, reads);
        //LITestRunner li_runner(runs_count, reads);
        //RITestRunner ri_runner(runs_count, reads);



        cout<<BlockSize<<" "<<lv_runner.run()<<" "<<rv_runner.run();
        //cout<<" "<<li_runner.run()<<" "<<ri_runner.run();

        if (LineWidth == 128)
        {
        	LSTestRunner ls_runner(runs_count, reads);
        	RSTestRunner rs_runner(runs_count, reads);
        	cout<<" "<<ls_runner.run()<<" "<<rs_runner.run();
        }

        cout<<endl;

        BlockSizeTest<typename BlockSizeList::Tail, LineWidth>::run(runs_count, reads);
    }
};


template <
        int LineWidth
>
class BlockSizeTest<NullType, LineWidth> {
public:
    static void run(int runs_count, int reads) {}
};

template <
        typename BlockSizeList,
        typename LineWidthList
>
class LineWidthTest {
    static const int LineWidth = LineWidthList::Head::Value;
    
public:
    static void run(int runs_count, int reads) {
        cout<<"#"<<LineWidth<<endl;
        BlockSizeTest<BlockSizeList, LineWidth>::run(runs_count, reads);
        cout<<endl;

        LineWidthTest<BlockSizeList, typename LineWidthList::Tail>::run(runs_count, reads);
        cout<<endl;
    }
};

template <
        typename BlockSizeList
>
class LineWidthTest<BlockSizeList, NullType> {
public:
    static void run(int runs_count, int reads) {}
};

template <int From, int To, typename ListType = NullType>
class ListBuilder {
    typedef TypeList<TypeCode<To>, ListType> NewList;
public:
    typedef typename ListBuilder<From, To / 2, NewList>::List List;
};

template <int From, typename Result>
class ListBuilder<From, From, Result> {
public:
    typedef TypeList<TypeCode<From>, Result> List;
};


int main(int argc, char** argv) {

    typedef ListBuilder<1, 128*1024>::List  	BlockSizeList;
    typedef ListBuilder<8, 512>::List   	LineWidthList;

    typedef LineWidthTest<BlockSizeList, LineWidthList> Test;

    Test::run(1, READ_COUNT);

    return 0;
}
